package tencent_practice;

import structure.TreeNode;

/**
 * 二叉搜索树的公共祖先
 */
public class Tencent_235_lowestCommonAncestor {
    /**
     * 各种情况精简之后糅合在一起
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || p == root || q == root) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        return root;
    }

    /**
     * 情况不糅合
     * @param root
     * @param p
     * @param q
     * @param noUse
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q, boolean noUse) {
        if (root == null) {
            return root;
        }
        if (root.val == p.val || root.val == q.val) {
            return root;
        }
        // 如果儿子在左子树
        if (findTreeNode(root.left, q) && findTreeNode(root.left, p)) {
            return lowestCommonAncestor(root.left, p, q, false);
        }
        // 如果儿子在右子树
        if (findTreeNode(root.right, q) && findTreeNode(root.right, p)) {
            return lowestCommonAncestor(root.right, p, q, false);
        }
        // 除去上面的两种情况，那后辈一定在根的左右子树中，则直接返回root
        return root;
    }

    private boolean findTreeNode(TreeNode root, TreeNode son) {
        if (root == null) {
            return false;
        }
        if (root.val == son.val) {
            return true;
        }
        return findTreeNode(root.left, son) || findTreeNode(root.right, son);
    }

}
